﻿//#include <set>
//void TestSet()
//{
//	// 用数组array中的元素构造set
//	int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
//6, 8, 0 };
//	set<int> s(array, array + sizeof(array) / sizeof(array));
//	cout << s.size() << endl;
//	// 正向打印set中的元素，从打印结果中可以看出：set可去重
//	for (auto& e : s)
//		cout << e << " ";
//	cout << endl;
//	// 使用迭代器逆向打印set中的元素
//	for (auto it = s.rbegin(); it != s.rend(); ++it)
//		cout << *it << " ";
//	cout << endl;
//	// set中值为3的元素出现了几次
//	cout << s.count(3) << endl;
//}




//#include <string>
//#include <map>
//void TestMap()
//{
//	map<string, string> m;
//	// 向map中插入元素的方式：
//	// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
//	m.insert(pair<string, string>("peach", "桃子"));
//	// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
//	m.insert(make_pair("banan", "香蕉"));
//
//	// 借用operator[]向map中插入元素
//	   /*
//	operator[]的原理是：
//	 用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
//	 如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
//	 如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
//	 operator[]函数最后将insert返回值键值对中的value返回
//	*/
//	// 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引
//	用结果，
//		m["apple"] = "苹果";
//	// key不存在时抛异常
//	//m.at("waterme") = "水蜜桃";
//	cout << m.size() << endl;
//	// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
//	for (auto& e : m)
//		cout << e.first << "--->" << e.second << endl;
//	cout << endl;
//	// map中的键值对key一定是唯一的，如果key存在将插入失败
//	auto ret = m.insert(make_pair("peach", "桃色"));
//	if (ret.second)
//		cout << "<peach, 桃色>不在map中, 已经插入" << endl;
//	else
//		cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
//		<< ret.first->second << " 插入失败" << endl;
//	// 删除key为"apple"的元素
//	m.erase("apple");
//	if (1 == m.count("apple"))
//		cout << "apple还在" << endl;
//	else
//		cout << "apple被吃了" << endl;
//}




//class Solution {
//public:
//	class Compare
//	{
//	public:
//		// 在set中进行排序时的比较规则
//		bool operator()(const pair<string, int>& left, const
//			pair<string, int>& right)
//		{
//			return left.second > right.second;
//		}
//	};
//	vector<string> topKFrequent(vector<string>& words, int k)
//	{
//		// 用<单词，单词出现次数>构建键值对，然后将vector中的单词放进去，统计每
//		个单词出现的次数
//			map<string, int> m;
//		for (size_t i = 0; i < words.size(); ++i)
//			++(m[words[i]]);
//		// 将单词按照其出现次数进行排序，出现相同次数的单词集中在一块
//		multiset<pair<string, int>, Compare> ms(m.begin(), m.end());
//		// 将相同次数的单词放在set中，然后再放到vector中
//		set<string> s;
//		size_t count = 0;   // 统计相同次数单词的个数
//		size_t leftCount = k;
//
//		vector<string> ret;
//		for (auto& e : ms)
//		{
//			if (!s.empty())
//			{
//				// 相同次数的单词已经全部放到set中
//				if (count != e.second)
//				{
//					if (s.size() < leftCount)
//					{
//						ret.insert(ret.end(), s.begin(), s.end());
//						leftCount -= s.size();
//						s.clear();
//					}
//					else
//					{
//						break;
//					}
//				}
//			}
//			count = e.second;
//			s.insert(e.first);
//		}
//		for (auto& e : s)
//		{
//			if (0 == leftCount)
//				break;
//			ret.push_back(e);
//			leftCount--;
//		}
//		return ret;
//	}
//};


//class Solution {
//public:
//	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//		// 先去重
//		set<int> s1;
//		for (auto e : nums1)
//		{
//			s1.insert(e);
//		}
//		set<int> s2;
//		for (auto e : nums2)
//		{
//			s2.insert(e);
//		}
//
//		// set排过序，依次比较，小的一定不是交集，相等的是交集
//		auto it1 = s1.begin();
//		auto it2 = s2.begin();
//		vector<int> ret;
//		while (it1 != s1.end() && it2 != s2.end())
//		{
//			if (*it1 < *it2)
//			{
//				it1++;
//			}
//			else if (*it2 < *it1)
//			{
//				it2++;
//			}
//			else
//			{
//				ret.push_back(*it1);
//				it1++;
//				it2++;
//			}
//		}
//		return ret;
//	}
//};

//bool Insert(const T& data)
//{
//	// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
//	// ...
//
//	// 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
//	破坏了AVL树
//		//   的平衡性
//
//	 /*
//	 pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
//	 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
//	  1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
//	  2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
//	  
//	 此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2
//	  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
//	成0，此时满足
//	     AVL树的性质，插入成功
//	  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
//	新成正负1，此
//	     时以pParent为根的树的高度增加，需要继续向上更新
//	  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进
//	行旋转处理
//	 */
//		while (pParent)
//		{
//			// 更新双亲的平衡因子
//			if (pCur == pParent->_pLeft)
//				pParent->_bf--;
//			else
//				pParent->_bf++;
//			// 更新后检测双亲的平衡因子
//			if (0 == pParent->_bf)
//			{
//				break;
//			}
//			else if (1 == pParent->_bf || -1 == pParent->_bf)
//			{
//				// 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲
//				为根的二叉树
//					// 的高度增加了一层，因此需要继续向上调整
//					pCur = pParent;
//				pParent = pCur->_pParent;
//			}
//			else
//			{
//				// 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以pParent
//				// 为根的树进行旋转处理
//				if (2 == pParent->_bf)
//				{
//					// ...
//				}
//				else
//				{
//					// ...
//				}
//			}
//		}
//	return true;
//}


//// 旋转之前，60的平衡因子可能是-1/0/1，旋转完成之后，根据情况对其他节点的平衡因子进
//行调整
//void _RotateLR(PNode pParent)
//{
//	PNode pSubL = pParent->_pLeft;
//	PNode pSubLR = pSubL->_pRight;
//
//	// 旋转之前，保存pSubLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节
//	点的平衡因子
//		int bf = pSubLR->_bf;
//
//	// 先对30进行左单旋
//	_RotateL(pParent->_pLeft);
//
//	// 再对90进行右单旋
//	_RotateR(pParent);
//	if (1 == bf)
//		pSubL->_bf = -1;
//	else if (-1 == bf)
//		pParent->_bf = 1;
//}



template<class ValueType>
class RBTree
{
	//……
	bool Insert(const ValueType& data)
	{
		PNode& pRoot = GetRoot();
		if (nullptr == pRoot)
		{
			pRoot = new Node(data, BLACK);
			// 根的双亲为头节点
			pRoot->_pParent = _pHead;
			_pHead->_pParent = pRoot;
		}
		else
		{
			// 1. 按照二叉搜索的树方式插入新节点
						// 2. 检测新节点插入后，红黑树的性质是否造到破坏，
			//   若满足直接退出，否则对红黑树进行旋转着色处理
		}
		// 根节点的颜色可能被修改，将其改回黑色
		pRoot->_color = BLACK;
		_pHead->_pLeft = LeftMost();
		_pHead->_pRight = RightMost();
		return true;
	}
private:
	PNode& GetRoot() { return _pHead->_pParent; }
	// 获取红黑树中最小节点，即最左侧节点
	PNode LeftMost();
	// 获取红黑树中最大节点，即最右侧节点
	PNode RightMost();
private:
	PNode _pHead;
};


